{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #验证回文串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #验证回文串 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非空字符串&nbsp;<code>s</code>，请判断如果&nbsp;<strong>最多 </strong>从字符串中删除一个字符能否得到一个回文字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = &quot;aba&quot;\n",
    "<strong>输出:</strong> true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = &quot;abca&quot;\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong> 可以删除 &quot;c&quot; 字符 或者 &quot;b&quot; 字符\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = &quot;abc&quot;\n",
    "<strong>输出:</strong> false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 680&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/valid-palindrome-ii/\">https://leetcode-cn.com/problems/valid-palindrome-ii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [RQku0D](https://leetcode.cn/problems/RQku0D/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [RQku0D](https://leetcode.cn/problems/RQku0D/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        i,j=0,len(s)-1\n",
    "        while(i<j):\n",
    "            if s[i]==s[j]:\n",
    "                i+=1\n",
    "                j-=1\n",
    "            else:\n",
    "                return s[i:j]==s[i:j][::-1] or s[i+1:j+1]==s[i+1:j+1][::-1]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, s: str) -> bool:\n",
    "        left,right = 0,len(s)-1\n",
    "        while left<right:\n",
    "            if s[left]==s[right]:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            else:return False\n",
    "        return True\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        left,right=0,len(s)-1\n",
    "        while left<right:\n",
    "            if s[left]!=s[right]:\n",
    "                sl = list(s)\n",
    "                sr = list(s)\n",
    "                sl.pop(left)\n",
    "                sr.pop(right)\n",
    "                return self.isPalindrome(''.join(sl)) or self.isPalindrome(''.join(sr))\n",
    "            left+=1\n",
    "            right-=1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def reversedstr(str):\n",
    "    list1=list(str)\n",
    "    if list1==list1[::-1]:\n",
    "        return True\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if reversedstr(s):\n",
    "            return True\n",
    "        i=0\n",
    "        j=len(s)-1\n",
    "        count=0\n",
    "        while i<=j:\n",
    "            if s[i]!=s[j]:\n",
    "                if reversedstr(s[i+1:j+1]) or reversedstr(s[i:j]):\n",
    "                    return True\n",
    "                else :\n",
    "                    return False\n",
    "            else:\n",
    "                i+=1\n",
    "                j-=1\n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def check(low,high):\n",
    "            i = low\n",
    "            j = high\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            \n",
    "            return True\n",
    "\n",
    "        \n",
    "        low = 0\n",
    "        high = len(s) - 1\n",
    "        while low < high:\n",
    "            if s[low] == s[high]:\n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else: # 最多删除一个字符\n",
    "                return check(low + 1,high) or check(low,high - 1)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def check(s):\n",
    "            n = len(s)\n",
    "            flag = True\n",
    "            l,r = 0,n-1\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "\n",
    "        n = len(s)\n",
    "        l,r = 0,n-1\n",
    "        while l < r:\n",
    "            if s[l] != s[r]:\n",
    "                return check(s[l+1:r+1]) or check(s[l:r])\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        n = len(s)\n",
    "        lens = n//2 if n%2 ==0 else n//2+1\n",
    "        for i in range(lens):\n",
    "            if s[i]!=s[-(i+1)]:\n",
    "                copy1,copy2=list(s),list(s)\n",
    "                copy1.pop(i)\n",
    "                copy2.pop(-(i+1))\n",
    "                if copy1 == copy1[::-1] or copy2 == copy2[::-1]:\n",
    "                    return True\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        a = '' #存放处理好的字符\n",
    "        for i in s: #遍历字符串 s，如果该字符是 '0'~'9'或者字母，就将它的小写形式放在 a里面\n",
    "            if (ord(i)>=48 and ord(i)<=57) or (ord(i)>=65 and ord(i)<=90) or (ord(i)>=97 and ord(i)<=122):\n",
    "                a = a + (i.lower())\n",
    "        # print(a)\n",
    "        if len(a)<=1: #如果处理完后的字符串长度不超过 1，说明为空或者单个字符，按定义是回文串\n",
    "            return True\n",
    "\n",
    "        for j in range(int(len(a)/2)): #遍历处理完后的字符串，一一判断前后对应的字符是否相等\n",
    "            # print(j, a[j], a[len(a)-1-j])\n",
    "            if a[j]==a[len(a)-1-j]:\n",
    "                continue\n",
    "            else:\n",
    "                b = a[:len(a)-1-j] + a[len(a)-1-j+1:]\n",
    "                # print(b)\n",
    "                if b[j:len(b)-1-j+1]==''.join(reversed(b[j:len(b)-1-j+1])):\n",
    "                    return True\n",
    "                else:\n",
    "                    break\n",
    "        \n",
    "        for j in range(int(len(a)/2)): #遍历处理完后的字符串，一一判断前后对应的字符是否相等\n",
    "            # print(j, a[j], a[len(a)-1-j])\n",
    "            if a[j]==a[len(a)-1-j]:\n",
    "                continue\n",
    "            else:\n",
    "                b = a[:j] + a[j+1:]\n",
    "                # print(b)\n",
    "                if b[j:len(b)-1-j+1]==''.join(reversed(b[j:len(b)-1-j+1])):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def is_pali_range(i, j):\n",
    "            return all(s[k] == s[j-k+i] for k in range(i, j))\n",
    "        \n",
    "        for i in range(len(s) // 2):\n",
    "            if s[i] != s[~i]:\n",
    "                j = len(s) - 1 - i\n",
    "                return is_pali_range(i+1, j) or is_pali_range(i, j-1)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if n <= 2:\n",
    "            return True\n",
    "\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                # 尝试删除左边字符或右边字符\n",
    "                delete_left = s[left+1:right+1]\n",
    "                delete_right = s[left:right]\n",
    "                if delete_left == delete_left[::-1] or delete_right == delete_right[::-1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if self.is_palindrome(s):\n",
    "            return True\n",
    "        for i in range(len(s) // 2):\n",
    "            if s[i] != s[len(s) - i - 1]:\n",
    "                if self.is_palindrome(s[:i] + s[i + 1:]):\n",
    "                    return True\n",
    "                if self.is_palindrome(s[:len(s) - i - 1] + s[len(s) - i:]):\n",
    "                    return True\n",
    "                break\n",
    "        return False\n",
    "\n",
    "    def is_palindrome(self, s: str) -> bool:\n",
    "        for i in range(len(s) // 2):\n",
    "            if s[i] != s[len(s) - i - 1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def ifhuiwen(s):\n",
    "            sl = len(s)\n",
    "            for index, c in enumerate(s):\n",
    "                if c == s[sl - index - 1]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return index\n",
    "                # if index >= len(s)/2:\n",
    "            return -1\n",
    "\n",
    "        kkk = ifhuiwen(s)\n",
    "        if kkk == -1:\n",
    "            return True\n",
    "        else:\n",
    "            s1 = s[:kkk] + s[kkk + 1:]\n",
    "            if ifhuiwen(s1) == -1:\n",
    "                return True\n",
    "            s2 = s[:len(s) - 1 - kkk] + s[len(s) - kkk:]\n",
    "            if ifhuiwen(s2) == -1:\n",
    "                return True\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def check(low, high):\n",
    "            i, j = low, high\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "        \n",
    "        low = 0\n",
    "        high = len(s) - 1\n",
    "        while low < high:\n",
    "            if s[low] == s[high]:\n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else:\n",
    "                return check(low+1, high) or check(low, high-1)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j and s[i] == s[j]:\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        if i >= j: return True\n",
    "        def check(l: int, r: int) -> bool:\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "        return check(i + 1, j) or check(i, j - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        \n",
    "        def recur(l, r):\n",
    "            if l >= r:\n",
    "                return True\n",
    "            \n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "        \n",
    "        n = len(s)\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return recur(i+1, j) or recur(i, j-1)\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def _validPalindrome(s, counter):\n",
    "            l, r = 0, len(s) - 1\n",
    "            while l <= r:\n",
    "                if s[l] == s[r]:\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    if counter <= 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        return _validPalindrome(s[l:r], counter - 1) or _validPalindrome(s[l + 1:r + 1],counter - 1)\n",
    "            return True\n",
    "        return _validPalindrome(s, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        res=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=res[i]:   \n",
    "                t1=s[:i]+s[i+1:]\n",
    "                t2=res[:i]+res[i+1:]\n",
    "                if t1==t1[::-1] or t2==t2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        leftI,leftJ = 0,n - 1\n",
    "        rightI,rightJ = 0,n - 1\n",
    "        leftCount = 0\n",
    "        rightCount = 0\n",
    "        while leftI < leftJ:\n",
    "            if s[leftI] != s[leftJ]:\n",
    "                leftCount += 1\n",
    "                leftI += 1\n",
    "                continue\n",
    "            \n",
    "            leftI += 1\n",
    "            leftJ -= 1\n",
    "\n",
    "       \n",
    "\n",
    "        while rightI < rightJ:\n",
    "            if s[rightI] != s[rightJ]:\n",
    "                rightCount += 1\n",
    "                if leftCount > 1 and rightCount > 1:\n",
    "                    return False\n",
    "                rightJ -= 1\n",
    "                continue\n",
    "            \n",
    "            rightI += 1\n",
    "            rightJ -= 1\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        pp=0\n",
    "        n = 0\n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "\n",
    "        while True:\n",
    "            if s[left] == s[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "                while left == n:\n",
    "                    left += 1\n",
    "                while right == n:\n",
    "                    right -= 1\n",
    "\n",
    "            else:\n",
    "                if n == 0:\n",
    "                    if s[left] == s[right - 1]:\n",
    "                        n = s[right]\n",
    "                        right -= 1\n",
    "                    elif s[left + 1] == s[right]:\n",
    "                        n = s[left]\n",
    "                        left += 1\n",
    "                    else:\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "            if left == right or left > right:\n",
    "                return True\n",
    "        pp=0\n",
    "        n = 0\n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "\n",
    "        while True:\n",
    "            if s[left] == s[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "                while left == n:\n",
    "                    left += 1\n",
    "                while right == n:\n",
    "                    right -= 1\n",
    "\n",
    "            else:\n",
    "                if n == 0:\n",
    "                    if s[left + 1] == s[right]:\n",
    "                        n = s[left]\n",
    "                        left += 1\n",
    "                    elif s[left] == s[right - 1]:\n",
    "                        n = s[right]\n",
    "                        right -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "                else:\n",
    "                    return False\n",
    "            if left == right or left > right:\n",
    "                return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            d = s[i]\n",
    "            t = s[::-1][i]\n",
    "            if d!=t:\n",
    "                s1 = s[0:i]+s[(i+1):n]\n",
    "                if s1==s1[::-1]:\n",
    "                    return True\n",
    "                s2 = s[::-1][0:i]+s[::-1][(i+1):n]\n",
    "                if s2==s2[::-1]:\n",
    "                    return True\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        low = 0\n",
    "        high = len(s) -1\n",
    "        while low < high:\n",
    "            if s[low] == s[high]:\n",
    "                low +=1\n",
    "                high -=1\n",
    "            else:\n",
    "                return self.checkPalind(s[low+1:high+1]) or self.checkPalind(s[low:high])\n",
    "        return True\n",
    "        \n",
    "\n",
    "\n",
    "    def checkPalind(self,s):\n",
    "        i,j = 0,len(s)-1\n",
    "        while i < j:\n",
    "            if s[i] !=s[j]:\n",
    "                return False\n",
    "            i +=1\n",
    "            j -=1\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def isPalindrome(s):\n",
    "            return s[::-1] == s\n",
    "\n",
    "        start = 0\n",
    "        end = len(s) - 1\n",
    "        while start <= end:\n",
    "            if s[start] == s[end]:\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            else:\n",
    "                return isPalindrome(s[start+1:end+1]) or isPalindrome(s[start:end])\n",
    "        return True \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n = len(s)\n",
    "        i, j = 0, n-1\n",
    "        while i< j:\n",
    "            if s[i] != s[j]:\n",
    "                ii, jj, flag = i, j-1, True\n",
    "                while ii< jj:\n",
    "                    if s[ii] != s[jj]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                    ii += 1\n",
    "                    jj -= 1\n",
    "                if flag:\n",
    "                    return True\n",
    "                ii, jj, flag = i+1, j, True\n",
    "                while ii< jj:\n",
    "                    if s[ii] != s[jj]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                    ii += 1\n",
    "                    jj -= 1\n",
    "                return flag\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        # 判断整个字符串是否为回文，如果是，则直接结束\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        \n",
    "        # 如果不是，要用左右双指针遍历\n",
    "        # 每次判断两个指针指向的字符是否相同，如果相同，则更新指针，\n",
    "        # 将left + 1, right - 1, 然后判断更新后的指针范围内的子串是否是回文字符串。\n",
    "        # 如果两个指针指向的字符不同，则两个字符中必须有一个被删除，此时我们就分成两种情况：\n",
    "            # ① 删除左指针对应的字符，留下子串 s[left+1:right+1]，\n",
    "            # ② 或者删除右指针对应的字符，留下子串 s[left:right]。\n",
    "        # 当这两个子串中至少有一个是回文串时，就说明原始字符串删除一个字符之后就以成为回文串。\n",
    "        left, right = 0, len(s) - 1\n",
    "        while left < right:\n",
    "            if s[left] == s[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                return s[left + 1:right + 1] == s[left + 1:right + 1][::-1] or s[left:right] == s[left:right][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "\n",
    "        def check(x, y):\n",
    "            while x < y:\n",
    "                if s[x] != s[y]:\n",
    "                    return False\n",
    "                x += 1\n",
    "                y -= 1\n",
    "            return True\n",
    "\n",
    "        n = len(s)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return check(i + 1, j) or check(i, j - 1)\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def checkPalindrome(low, high):\n",
    "            i, j = low, high\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "\n",
    "        low, high = 0, len(s) - 1\n",
    "        while low < high:\n",
    "            if s[low] == s[high]: \n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else:\n",
    "                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        \n",
    "        def is_valid(s, l, r):\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "        if is_valid(s, l, r):\n",
    "            return True\n",
    "        #print(l ,r)\n",
    "        while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    tempt = s[l]\n",
    "                    l += 1\n",
    "                    if is_valid(s, l, r):\n",
    "                        return True\n",
    "                    else:\n",
    "                        l -= 1\n",
    "                        r -= 1\n",
    "                        return is_valid(s, l, r)\n",
    "                l += 1\n",
    "                r -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        # 错误点：原本是回文的删除一个字符串必为回文。示例：aba删b;abba删b\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        # 特殊情况一头一尾去掉是否直接是回文串\n",
    "        if s[:-1] == s[:-1][::-1]:\n",
    "            return True\n",
    "        if s[1:] == s[1:][::-1]:\n",
    "            return True\n",
    "        start = 0\n",
    "        end = length - 1\n",
    "        while start < end:\n",
    "            if s[start] == s[end]:\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            else:\n",
    "                # 去头\n",
    "                temp_str01 = s[start+1:end + 1]\n",
    "                if temp_str01 == temp_str01[::-1]:\n",
    "                    return True\n",
    "                # 去尾\n",
    "                temp_str02 = s[start:end]\n",
    "                if temp_str02 == temp_str02[::-1]:\n",
    "                    return True\n",
    "                # 因为只能变1次。超过一次的直接返回False\n",
    "                return False\n",
    "        # for i in range(length):\n",
    "        #     # 错误点：特殊值i+1超限了\n",
    "        #     if i + 1 == length:\n",
    "        #         temp_str = s[:i]\n",
    "        #     else:\n",
    "        #         temp_str = s[:i] + s[i+1:]\n",
    "        #     if temp_str == temp_str[::-1]:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         continue\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        res=0\n",
    "        left=0\n",
    "        right=len(s)-1\n",
    "        def check(low,high):\n",
    "            i,j=low,high\n",
    "            while i<j:\n",
    "                if s[i]!=s[j]:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return True\n",
    "\n",
    "        while left<right:\n",
    "            if s[left]==s[right]:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            else:\n",
    "                return check(left+1,right) or check(left,right-1)\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def checkPalindrome(low, high):\n",
    "            i, j = low, high\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "\n",
    "        low, high = 0, len(s) - 1\n",
    "        while low < high:\n",
    "            if s[low] == s[high]: \n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else:\n",
    "                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        first=0\n",
    "        second=len(s)-1\n",
    "        while first<=second:\n",
    "            if s[first]==s[second]:\n",
    "                first+=1\n",
    "                second-=1\n",
    "            else:\n",
    "                re1=self.search(s, first+1, second)\n",
    "                if re1:\n",
    "                    return True\n",
    "                re2=self.search(s, first, second-1)\n",
    "                if re2:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "    def search(self, s, first, second):\n",
    "        while first<=second:\n",
    "            if s[first]==s[second]:\n",
    "                first+=1\n",
    "                second-=1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "        m = 0\n",
    "        while l < r:\n",
    "            l1 = l\n",
    "            r1 = r\n",
    "            if m > 1:\n",
    "                return False\n",
    "\n",
    "            if s[l] == s[r]:\n",
    "                l +=1\n",
    "                r -=1\n",
    "            else:\n",
    "                if s[l+1] == s[r]:\n",
    "                    if s[r-1] ==s[l]:\n",
    "                        while l1 < r1:\n",
    "                            if s[l1+1] == s[r1]:\n",
    "                                l1 += 1\n",
    "                                r1 -= 1\n",
    "                            else:\n",
    "                                r -= 2\n",
    "                                l += 1\n",
    "                                m += 1\n",
    "                                break\n",
    "                        else:\n",
    "                            l += 2\n",
    "                            r -= 1\n",
    "                            m += 1\n",
    "                    else:\n",
    "                        l += 2\n",
    "                        r -= 1\n",
    "                        m += 1\n",
    "                elif s[r-1] ==s[l]:\n",
    "                    r -= 2\n",
    "                    l += 1\n",
    "                    m += 1\n",
    "                else:\n",
    "                    return False\n",
    "        else:\n",
    "            if m > 1:\n",
    "                return False\n",
    "            else:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "        \n",
    "        for i in range(n//2):\n",
    "            if s[i] == s[n-1-i]:\n",
    "                continue\n",
    "            else:\n",
    "                if s[i+1:n-i] == s[i+1:n-i][::-1]:\n",
    "                    return True\n",
    "                if s[i:n-i-1] == s[i:n-i-1][::-1]:\n",
    "                    return True\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def check(s):\n",
    "            left = 0\n",
    "            right = len(s) - 1\n",
    "            while left < right:\n",
    "                if s[left] != s[right]:\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "        \n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                return check(s[left + 1:right + 1]) or check(s[left:right])\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        l,r = 0,len(s)-1\n",
    "        \n",
    "        def valid(s,l,r):\n",
    "            while l<r:\n",
    "                if s[l]!=s[r]:\n",
    "                    return False\n",
    "                l+=1\n",
    "                r-=1\n",
    "            return True\n",
    "\n",
    "        while l<r:\n",
    "            if s[l]==s[r]:\n",
    "                l+=1\n",
    "                r-=1\n",
    "            else:\n",
    "                return valid(s,l+1,r) or valid(s,l,r-1)\n",
    "        return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s == s[::-1]: return True\n",
    "        left, right = 0, len(s)-1\n",
    "        while left<=right:\n",
    "            if s[left]==s[right]:\n",
    "                left +=1\n",
    "                right -=1\n",
    "            else:\n",
    "                s2 = s[left+1:right+1]\n",
    "                s3 = s[left:right]\n",
    "                if s2 == s2[::-1] or s3 == s3[::-1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        length = len(s)\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        # 特殊情况一头一尾去掉是否直接是回文串\n",
    "        if s[:-1] == s[:-1][::-1]:\n",
    "            return True\n",
    "        if s[1:] == s[1:][::-1]:\n",
    "            return True\n",
    "        count = 0\n",
    "        start = 0\n",
    "        end = length - 1\n",
    "        while start < end:\n",
    "            if s[start] == s[end]:\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            else:\n",
    "                # 去头\n",
    "                temp_str01 = s[start+1:end + 1]\n",
    "                if temp_str01 == temp_str01[::-1]:\n",
    "                    return True\n",
    "                # 去尾\n",
    "                temp_str02 = s[start:end]\n",
    "                if temp_str02 == temp_str02[::-1]:\n",
    "                    return True\n",
    "                return False\n",
    "        # for i in range(length):\n",
    "        #     # 错误点：特殊值i+1超限了\n",
    "        #     if i + 1 == length:\n",
    "        #         temp_str = s[:i]\n",
    "        #     else:\n",
    "        #         temp_str = s[:i] + s[i+1:]\n",
    "        #     if temp_str == temp_str[::-1]:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         continue\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def checkpal(low,high):\n",
    "            i,j=low,high\n",
    "            while i <j:\n",
    "                if s[i]!=s[j]:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return True\n",
    "\n",
    "        low,high=0,len(s)-1\n",
    "        while low <high:\n",
    "            if s[low]==s[high]:\n",
    "                low+=1\n",
    "                high-=1\n",
    "            else:\n",
    "                return checkpal(low+1,high) or checkpal(low,high-1)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s[::-1] == s:return True\n",
    "        ns = s[::-1]\n",
    "        for i in range(len(s)):\n",
    "            if ns[i] != s[i]:\n",
    "                t1 = ns[:i]+ns[i+1:]\n",
    "                t2 = s[:i]+s[i+1:]\n",
    "                if t1[::-1] == t1 or t2[::-1] == t2:\n",
    "                    return True\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def f(l,r):\n",
    "            if s[l:r+1]==s[l:r+1][::-1]:\n",
    "                return True\n",
    "            return False\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            l=0\n",
    "            r=len(s)-1\n",
    "            while l<=r:\n",
    "                if s[l]!=s[r]:\n",
    "                    return f(l+1,r) or f(l,r-1)\n",
    "                l+=1\n",
    "                r-=1\n",
    "            return True\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "\n",
    "        n = len(s)\n",
    "        l, r = 0, n-1\n",
    "        while l <= r and s[l] == s[r]:\n",
    "            l += 1\n",
    "            r -= 1\n",
    "\n",
    "        if s[l] == s[r]:\n",
    "            return True\n",
    "        else:\n",
    "            tmp1 = s[:l] + s[l + 1:]\n",
    "            tmp2 = s[:r] + s[r + 1 :]\n",
    "            if tmp1 == tmp1[::-1] or tmp2 == tmp2[::-1]:\n",
    "                return True \n",
    "            else:\n",
    "                return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        \n",
    "        def is_valid(s, l, r):\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "        l = 0\n",
    "        r = len(s) - 1\n",
    "        if is_valid(s, l, r):\n",
    "            return True\n",
    "        #print(l ,r)\n",
    "        while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return is_valid(s, l + 1, r) or is_valid(s, l, r - 1)\n",
    "                l += 1\n",
    "                r -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        ns=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=ns[i]:\n",
    "                new1=s[:i]+s[i+1:]\n",
    "                new2=ns[:i]+ns[i+1:]\n",
    "            \n",
    "                if new1==new1[::-1] or new2==new2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                if s[:i] + s[i + 1:] == (s[:i] + s[i + 1:])[::-1]:\n",
    "                    return True\n",
    "                if s[:j] + s[j + 1:] == (s[:j] + s[j + 1:])[::-1]:\n",
    "                    return True\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPalind(s):\n",
    "    return s[::-1] == s\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        i, j = 0, len(s)-1\n",
    "        while i <= j:\n",
    "            if s[i] == s[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            else:\n",
    "                break\n",
    "        return isPalind(s[i+1:j+1]) or isPalind(s[i:j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:return True\n",
    "        left,right=0,n-1\n",
    "        while(left<right):\n",
    "            if s[left]==s[right]:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            else:\n",
    "                t1=s[left+1:right+1]\n",
    "                t2=s[left:right]\n",
    "                if t1==t1[::-1] or t2==t2[::-1]: return True\n",
    "                return False        \n",
    "        \n",
    "             \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def isPalindrome(x):\n",
    "            return x == x[::-1]\n",
    "        if isPalindrome(s): return True\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return isPalindrome(s[:i]+s[i+1:]) or isPalindrome(s[:j]+s[j+1:])\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def f(l,r):\n",
    "            if s[l:r+1]==s[l:r+1][::-1]:\n",
    "                return True\n",
    "            return False\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            l=0\n",
    "            r=len(s)-1\n",
    "            while l<=r:\n",
    "                if s[l]!=s[r]:\n",
    "                    if s[l+1:r+1]==s[l+1:r+1][::-1]:\n",
    "                        return True\n",
    "                    if  s[l:r]==s[l:r][::-1]:\n",
    "                        return True\n",
    "                    return False\n",
    "                l+=1\n",
    "                r-=1\n",
    "            return True\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        ns=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=ns[i]:\n",
    "                new1=s[:i]+s[i+1:]\n",
    "                new2=ns[:i]+ns[i+1:]\n",
    "            \n",
    "                if new1==new1[::-1] or new2==new2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        left, right = 0,len(s)-1\n",
    "        flag = True\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                flag = False\n",
    "                break\n",
    "            left = left+1\n",
    "            right = right-1\n",
    "        if flag:\n",
    "            return True\n",
    "        else:\n",
    "            left1,right1 = left + 1, right\n",
    "            left_flag = True\n",
    "            while left1< right1:\n",
    "                if s[left1] != s[right1]:\n",
    "                    left_flag = False\n",
    "                left1 = left1+1\n",
    "                right1 = right1 - 1\n",
    "\n",
    "            left2,right2 = left, right-1\n",
    "            right_flag = True\n",
    "            while left2 < right2:\n",
    "                if s[left2] != s[right2]:\n",
    "                    right_flag = False\n",
    "                left2= left2+1\n",
    "                right2= right2-1\n",
    "\n",
    "            return left_flag or right_flag\n",
    "            \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s==s[::-1]: return True\n",
    "        if not s: return False\n",
    "\n",
    "        left, right = 0, len(s)-1\n",
    "        while left<=right and s[left]==s[right]:\n",
    "            left +=1\n",
    "            right -=1\n",
    "        return s[left+1:right+1] == s[left+1:right+1][::-1] or s[left:right] == s[left:right][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def f(low,high):\n",
    "            i,j = low,high\n",
    "            while i<j:\n",
    "                if s[i]!=s[j]:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return True\n",
    "        low,high = 0,len(s)-1\n",
    "        while low<high:\n",
    "            if s[low]==s[high]:\n",
    "                low+=1\n",
    "                high-=1\n",
    "            else:\n",
    "                return f(low+1,high) or f(low,high-1)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if s[::-1]==s:\n",
    "            return True\n",
    "        else :\n",
    "            n=len(s)\n",
    "            ns=s[::-1]\n",
    "            for i in range(n):\n",
    "                if s[i]!=ns[i]:\n",
    "                    s1=s[:i]+s[i+1:]\n",
    "                    s2=ns[:i]+ns[i+1:]\n",
    "                    if s1==s1[::-1] or s2==s2[::-1]:\n",
    "                        return True\n",
    "                    else :\n",
    "                        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def checkPalindrome(low, high):\n",
    "            i, j = low, high\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return True\n",
    "\n",
    "        low, high = 0, len(s) - 1\n",
    "        while low < high:\n",
    "            if s[low] == s[high]: \n",
    "                low += 1\n",
    "                high -= 1\n",
    "            else:\n",
    "                return checkPalindrome(low + 1, high) or checkPalindrome(low, high - 1)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        left = 0 \n",
    "        right = len(s) - 1\n",
    "        while left <= right and s[right] == s[left]:\n",
    "            left+=1\n",
    "            right-=1\n",
    "        if left > right:\n",
    "           return True\n",
    "        else:\n",
    "            temp1 = s[:left] + s[left+1:]\n",
    "            temp2 = s[:right] + s[right+1:]\n",
    "            if temp1==temp1[::-1]:\n",
    "                return True\n",
    "            if temp2 == temp2[::-1]:\n",
    "                return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        # 方法：贪心。双指针向中间靠拢。遇到不一致的分两种情况。去头去尾分别判断是不是回文串。有一个就是True。都不是为False\n",
    "        length = len(s)\n",
    "        # 错误点：原本是回文的删除一个字符串必为回文。示例：aba删b;abba删b\n",
    "        if s == s[::-1]:\n",
    "            return True\n",
    "        # 特殊情况一头一尾去掉是否直接是回文串\n",
    "        if s[:-1] == s[:-1][::-1]:\n",
    "            return True\n",
    "        if s[1:] == s[1:][::-1]:\n",
    "            return True\n",
    "        start = 0\n",
    "        end = length - 1\n",
    "        while start < end:\n",
    "            if s[start] == s[end]:\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            else:\n",
    "                # 去头\n",
    "                temp_str01 = s[start+1:end + 1]\n",
    "                if temp_str01 == temp_str01[::-1]:\n",
    "                    return True\n",
    "                # 去尾\n",
    "                temp_str02 = s[start:end]\n",
    "                if temp_str02 == temp_str02[::-1]:\n",
    "                    return True\n",
    "                # 因为只能变1次。超过一次的直接返回False\n",
    "                return False\n",
    "        # for i in range(length):\n",
    "        #     # 错误点：特殊值i+1超限了\n",
    "        #     if i + 1 == length:\n",
    "        #         temp_str = s[:i]\n",
    "        #     else:\n",
    "        #         temp_str = s[:i] + s[i+1:]\n",
    "        #     if temp_str == temp_str[::-1]:\n",
    "        #         return True\n",
    "        #     else:\n",
    "        #         continue\n",
    "        # return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        left = 0\n",
    "        right = len(s) - 1\n",
    "        while left < right:\n",
    "            if s[left] != s[right]:\n",
    "                a = s[:left] + s[left+1:]\n",
    "                b = s[:right] + s[right+1:]\n",
    "                if b[::-1] == b or a[::-1] == a:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        ns=s[::-1]\n",
    "        if s==ns:return True\n",
    "        for i in range(len(s)):\n",
    "            if s[i]!=ns[i]:\n",
    "                ss=s[:i]+s[i+1:]\n",
    "                nss=ns[:i]+ns[i+1:]\n",
    "                if ss==ss[::-1] or nss==nss[::-1]:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        ns=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=ns[i]:\n",
    "                new1=s[:i]+s[i+1:]\n",
    "                new2=ns[:i]+ns[i+1:]\n",
    "            \n",
    "                if new1==new1[::-1] or new2==new2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        ns=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=ns[i]:\n",
    "                new1=s[:i]+s[i+1:]\n",
    "                new2=ns[:i]+ns[i+1:]\n",
    "            \n",
    "                if new1==new1[::-1] or new2==new2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        ns=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=ns[i]:\n",
    "                new1=s[:i]+s[i+1:]\n",
    "                new2=ns[:i]+ns[i+1:]\n",
    "            \n",
    "                if new1==new1[::-1] or new2==new2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        ns=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=ns[i]:\n",
    "                new1=s[:i]+s[i+1:]\n",
    "                new2=ns[:i]+ns[i+1:]\n",
    "            \n",
    "                if new1==new1[::-1] or new2==new2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def check(s,flag):\n",
    "            left = 0\n",
    "            right = len(s) - 1\n",
    "            while left < right:\n",
    "                if s[left] != s[right]:\n",
    "                    if flag:\n",
    "                        temp1 = list(s[:])\n",
    "                        temp1.pop(left)\n",
    "                        temp2 = list(s[:])\n",
    "                        temp2.pop(right)\n",
    "                        print(temp2,temp1)\n",
    "                        if check(temp1,False) or check(temp2,False):\n",
    "                            return True\n",
    "                    return False\n",
    "                left+=1\n",
    "                right -= 1\n",
    "            return True\n",
    "        return check(s,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        n=len(s)\n",
    "        if s==s[::-1]:\n",
    "            return True\n",
    "        ns=s[::-1]\n",
    "        for i in range(n):\n",
    "            if s[i]!=ns[i]:\n",
    "                new1=s[:i]+s[i+1:]\n",
    "                new2=ns[:i]+ns[i+1:]\n",
    "            \n",
    "                if new1==new1[::-1] or new2==new2[::-1]: \n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        def judge(s):\n",
    "            if len(s) == 1:return True\n",
    "            if len(s) == 2:\n",
    "                if s[0] == s[1]:return True\n",
    "                else:return False\n",
    "            for i in range(0,len(s)//2):\n",
    "                            if s[i] == s[len(s)-1-i]:\n",
    "                                continue\n",
    "                            else:\n",
    "                                return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        tmp = \"\"\n",
    "        for i in s:\n",
    "            tmp += i\n",
    "        tmp = list(tmp)\n",
    "        s = list(s)\n",
    "        for i in range(len(s)//2):\n",
    "                if s[i] == s[len(s)-1-i]:\n",
    "                    continue\n",
    "                else:\n",
    "                    # a = s.pop(i)\n",
    "                    # b = tmp.pop(len(tmp)-1-i)\n",
    "                    return judge(s[i+1:len(s)-i]) or judge(s[i:len(s)-1-i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        slist = list(s)\n",
    "        if slist[:] == slist[::-1]:\n",
    "            return True\n",
    "        slen = len(s)\n",
    "        start , end = 0, slen - 1\n",
    "        while start < end:\n",
    "            if slist[start] !=slist[end]:\n",
    "                return slist[start + 1:end] == slist[end:start + 1:-1] or slist[start:end - 1] == slist[end - 1:start:-1]\n",
    "            start += 1\n",
    "            end -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def validPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def check_P(s):\n",
    "            n = len(s)\n",
    "            head = 0\n",
    "            rear = n - 1\n",
    "\n",
    "            while head < rear:\n",
    "                if s[head]==s[rear]:\n",
    "                    head = head + 1\n",
    "                    rear = rear - 1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        n = len(s)\n",
    "        head = 0\n",
    "        rear = n - 1\n",
    "        s = list(s)\n",
    "\n",
    "        while head < rear:\n",
    "            if s[head]==s[rear]:\n",
    "                head = head + 1\n",
    "                rear = rear - 1\n",
    "            else: # 发现头尾元素不相等\n",
    "                t1 = s[head+1:rear+1] #去掉头\n",
    "                t2 = s[head:rear] #去掉尾\n",
    "\n",
    "                if check_P(t1)==True or check_P(t2)==True: # 如果去掉头是回文或者去掉尾是回文，那就是true\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if len(s) <= 2 : #特殊情况\n",
    "            return True\n",
    "        i,j = 0,len(s) - 1\n",
    "        s = list(s)\n",
    "        while i < j :\n",
    "            if s[i] != s[j] :\n",
    "                l_s = copy.copy(s)\n",
    "                r_s = copy.copy(s)\n",
    "                l_s.pop(i)\n",
    "                r_s.pop(j)\n",
    "                print(l_s)\n",
    "                print(r_s)\n",
    "                if l_s == l_s[::-1] or r_s == r_s[::-1]:\n",
    "                    return True\n",
    "                else :\n",
    "                    return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isNum(s):\n",
    "    if(s>='0' and s<='9'):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def isChar1(s):\n",
    "    if(s>='A' and s<='Z'):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def isChar2(s):\n",
    "    if(s>='a' and s<='z'):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "def isPalindrome(s):\n",
    "    s1=[]\n",
    "    l=len(s)\n",
    "    for i in range(l):\n",
    "        if(isNum(s[i]) or isChar1(s[i]) or isChar2(s[i])):\n",
    "            if(isChar1(s[i])):\n",
    "                s1.append(chr(ord(s[i])+32))\n",
    "            else:\n",
    "                s1.append(s[i])\n",
    "    l2=len(s1)\n",
    "    p=0\n",
    "    q=l2-1\n",
    "    #print(s1)\n",
    "    while(p<=q):\n",
    "        if(s1[p]==s1[q]):\n",
    "            p+=1\n",
    "            q-=1\n",
    "        else:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        if(isPalindrome(s)):\n",
    "            return True\n",
    "        l=len(s)\n",
    "        p=0\n",
    "        q=l-1\n",
    "        while(p<=q):\n",
    "            if(s[p]==s[q]):\n",
    "                p+=1\n",
    "                q-=1\n",
    "            else:\n",
    "                temp1=list(s)\n",
    "                temp1[p]=\" \"\n",
    "                temp2=list(s)\n",
    "                temp2[q]=\" \"\n",
    "                if(isPalindrome(\"\".join(temp1)) or isPalindrome(\"\".join(temp2))):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        s = s.lower()\n",
    "        new_s = \"\"\n",
    "        for i in s:\n",
    "            if i.isalnum():\n",
    "                new_s += i\n",
    "        left = 0\n",
    "        right = len(new_s) - 1\n",
    "        while left < right and new_s[left] == new_s[right]:\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        if new_s[left] == new_s[right]:\n",
    "            return True\n",
    "        else:\n",
    "            tmp = new_s[:left] + new_s[left + 1:]\n",
    "            if tmp == tmp[::-1]:\n",
    "                return True\n",
    "            tmp = new_s[:right] + new_s[right + 1:]\n",
    "            if tmp == tmp[::-1]:\n",
    "                return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validPalindrome(self, s: str) -> bool:\n",
    "        rever = s[::-1]\n",
    "        if s == rever:\n",
    "            return True\n",
    "        for i in range(len(s)):\n",
    "            if s[i] != rever[i]:\n",
    "                news = s[:i:] + rever[i+1::]\n",
    "                news_1 = rever[:i:] + s[i+1::]\n",
    "        if news == news[::-1] or news_1 == news_1[::-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
